package com.example.lcpractice.binarytree;

import com.example.lcpractice.datastructure.TreeNode;

import java.util.Arrays;

/**
 * 题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列
 * {1，2，4，7，3，5，6，8}和中序遍历序列{4，7，2，1，5，3，8，6}，则重建二叉树并返回。
 *
 * @author hd
 * @date 2022/2/25 13:51
 */
public class ReBinaryTree {
    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] mid = {4, 7, 2, 1, 5, 3, 8, 6};

        System.out.println(reconstruct2(pre, mid));


    }


    //  解法一：递归（传入数组的拷贝）
    public static TreeNode reconstruct(int[] pre, int[] mid) {
        if (pre == null || mid == null || pre.length < 1 || mid.length < 1) {
            return null;
        }
        if (pre.length != mid.length) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        for (int i = 0; i < pre.length; i++) {
            if (pre[0] == mid[i]) {
                root.setLeft(reconstruct(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(mid, 0, i)));
                root.setRight(reconstruct(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(mid, i + 1, mid.length)));
            }
        }
        return root;

    }


    public static TreeNode reconstruct2(int[] pre, int[] mid) {
        if (pre == null || mid == null || pre.length < 1 || mid.length < 1) {
            return null;
        }
        if (pre.length != mid.length) {
            return null;
        }

        return helper(pre, 0, pre.length - 1, mid, 0, mid.length - 1);

    }

    private static TreeNode helper(int[] pre, int preL, int preR, int[] mid, int midL, int midR) {
        if (preL > preR || midL > midR) {
            return null;
        }
        final int rootVal = pre[preL];
        int index = 0;
        while (index <= midR && mid[index] != rootVal) {
            index++;
        }
        TreeNode root = new TreeNode(rootVal);
        root.setLeft(helper(pre, preL + 1, preL - midL + index, mid, midL, index));
        root.setRight(helper(pre, preL - midL + index + 1, preR, mid, index + 1, midR));
        return root;
    }

}
